<!DOCTYPE html>
<html lang="en">

<head>
    <meta name="generator" content="Hugo 0.73.0" />
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<meta name="author" content="Ap Chen ">
<meta name="description" content="Algorithms 4th Robert Sedgewick. Kevin Wayne 正则表达式是一种进行非确定性模式匹配的方式。 算法只是根基，是数理理论与工程学层次框架下的活的灵魂，也是培养系统观的产物。 正则表达" />
<meta name="keywords" content="blog" />
<meta name="robots" content="noodp" />

<link rel="canonical" href="https://fziks.gitee.io/blog/regular-expression/" />

<meta itemprop="name" content="深入理解正则表达式">
<meta itemprop="description" content="Algorithms 4th Robert Sedgewick. Kevin Wayne 正则表达式是一种进行非确定性模式匹配的方式。 算法只是根基，是数理理论与工程学层次框架下的活的灵魂，也是培养系统观的产物。 正则表达">
<meta itemprop="datePublished" content="2020-08-19T00:00:00&#43;00:00" />
<meta itemprop="dateModified" content="2020-08-19T00:00:00&#43;00:00" />
<meta itemprop="wordCount" content="3673">



<meta itemprop="keywords" content="Algorithms," />
<meta property="og:title" content="深入理解正则表达式" />
<meta property="og:description" content="Algorithms 4th Robert Sedgewick. Kevin Wayne 正则表达式是一种进行非确定性模式匹配的方式。 算法只是根基，是数理理论与工程学层次框架下的活的灵魂，也是培养系统观的产物。 正则表达" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://fziks.gitee.io/blog/regular-expression/" />
<meta property="article:published_time" content="2020-08-19T00:00:00+00:00" />
<meta property="article:modified_time" content="2020-08-19T00:00:00+00:00" />

<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="深入理解正则表达式"/>
<meta name="twitter:description" content="Algorithms 4th Robert Sedgewick. Kevin Wayne 正则表达式是一种进行非确定性模式匹配的方式。 算法只是根基，是数理理论与工程学层次框架下的活的灵魂，也是培养系统观的产物。 正则表达"/>


<link rel="apple-touch-icon" sizes="60x60" href="https://fziks.gitee.io/icons/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="https://fziks.gitee.io/icons/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="https://fziks.gitee.io/icons/favicon-16x16.png">
<link rel="manifest" href="https://fziks.gitee.io/icons/site.webmanifest">
<link rel="mask-icon" href="https://fziks.gitee.io/icons/safari-pinned-tab.svg" color="#5bbad5">
<link rel="shortcut icon" href="https://fziks.gitee.io/icons/favicon.ico">
<meta name="msapplication-TileColor" content="#ffffff">
<meta name="msapplication-config" content="/icons/browserconfig.xml">
<meta name="theme-color" content="#ffffff">

<title>深入理解正则表达式</title>


<link rel="stylesheet" href="//at.alicdn.com/t/font_1559566_wk214kwa2dn.css">


    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.11.1/dist/katex.min.css" integrity="sha384-zB1R0rpPzHqg7Kpt0Aljp8JPLqbXI3bhnPWROx27a9N0Ll6ZP/+DiW/UqRcLbRjq" crossorigin="anonymous">



    
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/normalize/8.0.1/normalize.css" integrity="sha256-WAgYcAck1C1/zEl5sBl5cfyhxtLgKGdpI3oKyJffVRI=" crossorigin="anonymous" />
    
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.7.2/animate.css" integrity="sha256-a2tobsqlbgLsWs7ZVUGgP5IvWZsx8bTNQpzsqCSm5mk=" crossorigin="anonymous" />
    
   <link href="https://stackpath.bootstrapcdn.com/bootswatch/4.4.1/materia/bootstrap.min.css" rel="stylesheet" integrity="sha384-1tymk6x9Y5K+OF0tlmG2fDRcn67QGzBkiM3IgtJ3VrtGrIi5ryhHjKjeeS60f1FA" crossorigin="anonymous">
    
    
    <link rel="stylesheet" href="https://fziks.gitee.io/sass/main_cdn.min.270b43bb8631af4497ed45b90db42c517e86c9511418de9152f134d02ed32b87.min.2192baea245cf318085511589e62bfbdb3fbe4fb0eef718f1be9af91c10542ce.css" integity="sha256-IZK66iRc8xgIVRFYnmK/vbP75PsO73GPG&#43;mvkcEFQs4=">

</head>

<body class="ready bg-site" id="page" data-gr-c-s-loaded="true">
    <header id="header-main" class="header">
    <nav class="navbar navbar-horizontal navbar-expand-lg shadow-sm navbar-light bg-white">
        <div class="container-fluid">
            <a class="navbar-brand" href="https://fziks.gitee.io/">Ap Chen</a>
            <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbar-primary"
                aria-controls="navbar-primary" aria-expanded="false" aria-label="Toggle navigation">
                <span class="navbar-toggler-icon"></span>
            </button>
            <div class="collapse navbar-collapse" id="navbar-primary" style>
                <ul class="navbar-nav ml-lg-auto">
                    
                    <li class="nav-item">
                        <a class="btn btn-sm btn-animated btn-animated-y" href="https://fziks.gitee.io/blog/">
                            <span class="btn-inner--visible">
                                <i class="iconfont icon-blog"></i>
                                blog
                            </span>
                            <span class="btn-inner--hidden">博客</span>
                        </a>
                    </li>
                    
                    <li class="nav-item">
                        <a class="btn btn-sm btn-animated btn-animated-y" href="https://fziks.gitee.io/notes/">
                            <span class="btn-inner--visible">
                                <i class="iconfont icon-Notes"></i>
                                notes
                            </span>
                            <span class="btn-inner--hidden">笔记</span>
                        </a>
                    </li>
                    
                    <li class="nav-item">
                        <a class="btn btn-sm btn-animated btn-animated-y" href="https://fziks.gitee.io/about/">
                            <span class="btn-inner--visible">
                                <i class="iconfont icon-aboutus"></i>
                                about
                            </span>
                            <span class="btn-inner--hidden">关于我</span>
                        </a>
                    </li>
                    
                    <li class="nav-item">
                        <div class="dropdown">
                            <button class="btn btn-sm btn-animated btn-animated-y" type="button" id="nav-social"
                                data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
                                <span class="btn-inner--visible">
                                    <i class="iconfont icon-social"></i> Social
                                </span>
                                <span class="btn-inner--hidden">联系方式</span>
                            </button>
                            <div class="dropdown-menu dropdown-menu-right" aria-labelledby="dropdownMenuButton">
                                
                                <a class="dropdown-item btn btn-sm btn-icon" href="https://github.com/littlegreedy/" target="_blank" rel="noopener me"
                                    title="Github">
                                    <span class="btn-inner--icon mr-2"><i class="iconfont icon-github"></i></span>
                                    Github
                                </a>
                                
                                <a class="dropdown-item btn btn-sm btn-icon" href="mailto:littlegreedy@qq.com" target="_blank" rel="noopener me"
                                    title="Email">
                                    <span class="btn-inner--icon mr-2"><i class="iconfont icon-email"></i></span>
                                    email
                                </a>
                                
                            </div>
                        </div>
                    </li>
                    <li class="nav-item">
                        <div class="dropdown">
                            <button class="btn btn-sm btn-animated btn-animated-y" type="button" id="nav-menu"
                                data-toggle="dropdown" aria-haspopup="true" aria-expanded="false">
                                <span class="btn-inner--visible">
                                    <i class="iconfont icon-more"></i> Extra
                                </span>
                                <span class="btn-inner--hidden">其他内容</span>
                            </button>
                            <div class="dropdown-menu dropdown-menu-right" aria-labelledby="dropdownMenuButton">
                                
                                <a class="dropdown-item btn btn-sm btn-animated btn-animated-x"
                                    href="https://fziks.gitee.io/bangumi/">
                                    <span class="btn-inner--visible">
                                        <i class="iconfont icon-bilibili-line"></i> bangumi
                                    </span>
                                    <span class="btn-inner--hidden">追番列表</span>
                                </a>
                                
                                <a class="dropdown-item btn btn-sm btn-animated btn-animated-x"
                                    href="https://fziks.gitee.io/friends/">
                                    <span class="btn-inner--visible">
                                        <i class="iconfont icon-friend"></i> friends
                                    </span>
                                    <span class="btn-inner--hidden">友链</span>
                                </a>
                                
                                <a class="dropdown-item btn btn-sm btn-animated btn-animated-x"
                                    href="https://fziks.gitee.io/slides/">
                                    <span class="btn-inner--visible">
                                        <i class="iconfont icon-resources"></i> resources
                                    </span>
                                    <span class="btn-inner--hidden">资源</span>
                                </a>
                                
                                <a class="dropdown-item btn btn-sm btn-animated btn-animated-x"
                                    href="https://fziks.gitee.io/search/">
                                    <span class="btn-inner--visible">
                                        <i class="iconfont icon-search"></i> Search
                                    </span>
                                    <span class="btn-inner--hidden">站内搜索</span>
                                </a>
                                
                                <a class="dropdown-item btn btn-sm btn-animated btn-animated-x"
                                    href="https://fziks.gitee.io/portal/">
                                    <span class="btn-inner--visible">
                                        <i class="iconfont icon-iconentrance"></i> Portal
                                    </span>
                                    <span class="btn-inner--hidden">自定门户</span>
                                </a>
                                
                            </div>
                        </div>
                    </li>
                </ul>
            </div>
        </div>
    </nav>
</header>

    
<div class="container rounded bg-gradient-secondary">
    <div class="row my-lg-5">
        <div class="col p-5 text-center">
            <h1>深入理解正则表达式</h1>
            <div>
                
                <p>
                    <i class="iconfont icon-NewFile mr-2"></i>
                    2020-08-19 08:00 CST
                </p>
                
                <p>
                    <i class="iconfont icon-modify mr-2"></i>
                    2020-08-19 08:00 CST
                </p>
            </div>
            <a href="../" class="tongue tongue-secondary tongue-bottom d-print-none">
                <i class="iconfont icon-angle-up-o"></i>
            </a>
        </div>
    </div>
</div>
<div id="content" class="my-3">


  <div class="container">



    

    
 	 
      <div class="col col-12 col-lg-6 d-print-none">
        <div id="toc" class="card w-100 shadow-none">
          <div class="card-body">
            <h4 class="card-title pb-0">目录</h4>
            <nav id="TableOfContents">
  <ul>
    <li><a href="#正则表达式的部分应用">正则表达式的部分应用</a></li>
    <li><a href="#正则描述模式">正则描述模式</a>
      <ul>
        <li><a href="#正则表达式的形式语义">正则表达式的形式语义</a></li>
      </ul>
    </li>
    <li><a href="#缩略写法">缩略写法</a>
      <ul>
        <li></li>
      </ul>
    </li>
    <li><a href="#有穷自动机">有穷自动机</a></li>
    <li><a href="#非确定有限状态自动机">非确定有限状态自动机</a></li>
    <li><a href="#模拟nfa运行">模拟NFA运行</a>
      <ul>
        <li></li>
      </ul>
    </li>
    <li><a href="#构造与正则表达式对应的nfa">构造与正则表达式对应的NFA</a></li>
  </ul>
</nav>
          </div>
        </div>
      </div>
      

    <div class="row row-grid justify-content-center">

   

      <div class="col col-12 col-lg-10">
        <div class="card border-0 shadow-none">
          <div class="card-body">
            
            
            
            
              
            
            
              
            
            
              
            
            <p>Algorithms 4th  Robert Sedgewick. Kevin Wayne</p>
<p>正则表达式是一种进行<strong>非确定性</strong>模式匹配的方式。</p>
<p>算法只是根基，是数理理论与工程学层次框架下的活的灵魂，也是培养系统观的产物。</p>
<h2 id="正则表达式的部分应用">正则表达式的部分应用<a href="#正则表达式的部分应用" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h2>
<p>理论计算机科学的第一堂入门课程就应该是找出正则表达式所能指定的语言集合。你可能会意外它可以进行取余操作：$ (0 | 1( 01 * 0)*1)*$描述的所有由0和1组成的字符串都是3的倍数的二进制表示！11、110、1001和1100都在这个语言中。</p>
<p>正则表达式可以高效、简洁地描述处理词法单元时用到的模式类型。</p>
<h2 id="正则描述模式">正则描述模式<a href="#正则描述模式" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h2>
<p>语言指代一个字符串的集合，模式指代一种特定语言的详细规格说明。模式的描述由3种基本操作和作为操作数的字符组成，与大家熟悉的算术表达式的规则十分类似。</p>
<p><strong>连接操作</strong>：AB； 当我们写出AB时，就定义了它是含有A和B连接而成的字符串。</p>
<p><strong>或操作</strong>： 可以指定多种可能的匹配。用竖线来表示：A|E|I|O|U 为指定任选其中一个。<strong>连接操作</strong>的优先级高于<strong>或操作</strong>，因此AB|BCD指定的集合是{AB,BCD}；或操作是唯一的二元操作符，这将为后续代码实现的间简洁性埋下重要伏笔。</p>
<p><strong>闭包操作</strong>：可以将模式的部分重复任意的次数。模式闭包是将自身连接任意多次（包括零次）得到的字符串集合。我们将 * 标记在需要被重复的模式之后，以表示闭包。闭包操作的优先级高于连接操作，因此 AB*是由A和0个或多个B的字符串组成。</p>
<p><strong>括号</strong>：改变默认的优先级顺序！如(AB)*是由将AB连接的任意多次得到的所有字符串和空字符串组成的 {$\epsilon$ , AB , ABAB , ...}。空字串的记号是$\epsilon$ 。</p>
<h3 id="正则表达式的形式语义">正则表达式的形式语义<a href="#正则表达式的形式语义" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h3>
<ul>
<li>空字符串$\epsilon$</li>
<li>单个字符</li>
<li>包含在括号中的另一个正则表达式</li>
<li>两个或多个连接起来的正则表达式</li>
<li>由或运算符分割的两个或多个正则表达式</li>
<li>由闭包运算标记的一个正则表达式</li>
</ul>
<p>描述一种语言可以有许多中不同的方法，我们必须给出最简洁的模式，进而实现高效算法一样。</p>
<ul>
<li>语言运算
<ul>
<li>$L\cup M$</li>
<li>$LM$</li>
<li>$L^*=\cup_{i=0}^\infty L^i$</li>
<li>$L^+=\cup_{i=1}^\infty L^i$</li>
</ul>
</li>
<li>正则表达式
<ul>
<li>基本部分
<ul>
<li><em>ε</em>是一个正则表达式，$L(\epsilon)={\epsilon}$</li>
<li>$如果a是\Sigma上的一个符号，那么a是正则表达式，L(a)={a}$</li>
</ul>
</li>
<li>递归定义
<ul>
<li>$L((r)|(s))=L(r)\cup L(s)$</li>
<li>$L((r)(s))=L(r)L(s)$</li>
<li>$L((r)^*)=L(r)^*$</li>
<li>$L((r))=L(r)$</li>
</ul>
</li>
<li>运算优先级 $*$ &gt;连接 &gt; $|$</li>
<li>扩展
<ul>
<li>$r+$ = $rr^*$</li>
<li>$r?$ = $\epsilon|r$</li>
<li>$[a_1\cdots a_n]$ = $a_1|a_2\cdots|a_n$</li>
</ul>
</li>
</ul>
</li>
<li>正则集合：可以用正则表达式定义的语言</li>
<li>正则定义：$d_1\rightarrow r_1$
<ul>
<li>不能重复定义，不能与字母表重复</li>
</ul>
</li>
</ul>
<h2 id="缩略写法">缩略写法<a href="#缩略写法" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h2>
<p>一般程序都在基本规则的基础上增加了各种额外的规则，以力求简洁地描述实际应用中所需的语言。我们会发现限制一件事物，往往能获得意想不到的收益，如同上世纪60年代针对与结构化设计原理有悖的goto语句的颠覆。下面是一些基本操作的实用扩展（缩略写法），能简洁地写出强大的模式。</p>
<h4 id="字符集描述符">字符集描述符<a href="#字符集描述符" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h4>
<p>只要一两个字符来直接表示一系列字符集时常能带来方便</p>
<table>
<thead>
<tr>
<th>名称</th>
<th>记法</th>
<th>举例</th>
</tr>
</thead>
<tbody>
<tr>
<td>通配符</td>
<td>.</td>
<td>A.B</td>
</tr>
<tr>
<td>指定集合</td>
<td>[] 括住的字符</td>
<td>[AEIOU]*</td>
</tr>
<tr>
<td>范围集合</td>
<td>[] 括住的字符，由 - 分隔</td>
<td>[AB] [ 0-9]</td>
</tr>
<tr>
<td>补集</td>
<td>[] 括住的字符，首字符为 ^</td>
<td>[^AEIOU]*</td>
</tr>
</tbody>
</table>
<h4 id="闭包的简写">闭包的简写<a href="#闭包的简写" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h4>
<p>实际应用中，我们不仅希望能复制任意多次，更愿意可以灵活指定重复的次数或范围。</p>
<table>
<thead>
<tr>
<th>名称</th>
<th>记法</th>
<th>举例</th>
</tr>
</thead>
<tbody>
<tr>
<td>至少重复一次</td>
<td>+</td>
<td>(AB)+</td>
</tr>
<tr>
<td>重复0或1次</td>
<td>？</td>
<td>(AB)?</td>
</tr>
<tr>
<td>重复指定次数</td>
<td>{次数}</td>
<td>(AB){3}</td>
</tr>
<tr>
<td>重复指定范围的次数</td>
<td>{范围}</td>
<td>(AB){1-2}</td>
</tr>
</tbody>
</table>
<h4 id="转义序列">转义序列<a href="#转义序列" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h4>
<p>以上用到的构造正则表达式的特殊字符称为<strong>元字符</strong>，我们开头加上反斜杠开头的转义序列来区分元字符和字母表中的字符。</p>
<h2 id="有穷自动机">有穷自动机<a href="#有穷自动机" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h2>
<ul>
<li>本质上和状态转换图相同，但有穷自动机只回答Yes/No
<ul>
<li>不确定的有穷自动机（NFA）：边上的标号没有限制，一个符号可出现在离开同一个状态的多条边上，ε可以做标号</li>
<li>确定的有穷自动机（DFA）：对于每个状态和没个符号，有且只有一条边</li>
</ul>
</li>
<li>两种自动机都识别正则语言
<ul>
<li>对于每个可以用正则表达式描述的语言，均可用某个NFA或DFA来识别；反之亦然</li>
</ul>
</li>
</ul>
<p>NFA的定义：</p>
<ul>
<li>一个有穷的状态集合S<em>S</em></li>
<li>一个输入符号集合\SigmaΣ</li>
<li>转换函数：对于每个状态和符号，给出相应的后继状态集合</li>
<li>S<em>S</em>中的某个状态s_0<em>s</em>0被指定为开始状态/初始状态</li>
<li>S<em>S</em>的一个子集F<em>F</em>被指定为接受状态集合</li>
</ul>
<p>NFA的表示方式：</p>
<ul>
<li>状态转换图</li>
<li>转换表</li>
</ul>
<p>一个NFA能够接受字符串，当且仅当对应的转换图中存在一条从开始状态到某个接受状态的路径，且该路径各条边上的标号按顺序组成该字符串。</p>
<p>NFA接受的语言：从开始状态到达接受状态的所有路径的标号串的集合，即该NFA接受的字符串的集合。</p>
<p>一个NFA被称为DFA，如果</p>
<ul>
<li>
<p>没有标号为$\varepsilon$的转换，并且</p>
</li>
<li>
<p>对于每个状态s和每个输入符号a，有且仅有一条标号为a<em>的离开s</em>的边</p>
</li>
</ul>
<h2 id="非确定有限状态自动机">非确定有限状态自动机<a href="#非确定有限状态自动机" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h2>
<p>相比KMP的有限状态自动机可根据文本中的字符改变自身的状态，当且仅当自动机达到停止状态时它找到匹配或确定不匹配，每种状态的转换完全由文本中的字符决定，是确定的。而正则表达式则要一种更加强大的抽象自动机，因为或操作的存在，自动机无法根据一个字符就判断出模式是否出现；因为闭包存在，自动机甚至无法知道需要检查多少字符才会出现匹配失败。为了克服这一困难，我们需要<strong>非确定性的自动机</strong>（<a href="http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton">NFA</a> ）。</p>
<blockquote>
<p>kleene定理 是理论计算机科学中一个重要结论，它证明了对于任意正则表达式都存在一个 与之对应的非确定有限状态自动机（反之亦然）。</p>
</blockquote>
<p>正则表达式模式匹配程序的总体结构与KMP算法基本一致：</p>
<ul>
<li>构造和给定正则表达式相对应的非确定有限状态自动机</li>
<li>模拟NFA在给定文本上的运行轨迹</li>
</ul>
<p>我们来看看NFA的性质和操作，NFA是用来判断一段文本是否包含在正则表达式所描述的语言中。</p>
<p>NFA有着以下特点：</p>
<ul>
<li>长度为M的正则表达式中的每个字符在所对应的NFA中都有且只有一个对应的状态。NFA的起始状态为0并含有一个（虚拟的）接受状态M。</li>
<li>字母表中的字符所对应的状态都有一条从它指向的边，这条边指向模式中的下一个字符所对的状态。</li>
<li>元字符&quot; ( &quot;，&quot; ) &quot;，&quot; | &quot;和&quot; * &quot;所对应的状态至少含有一条指出的边（红色边）</li>
<li>有些状态有多条指出的边，但一个状态只能有一条指出的黑色边</li>
</ul>
<p>例子： $((A*B|AC)D)$所对应的NFA  （约定所有模式包含在括号里）</p>
<p><img src="https://cdn.jsdelivr.net/gh/littlegreedy/zero/img/pic/image-20200819194222020.png" alt=""></p>
<p>这里引入两种状态转换</p>
<ul>
<li>匹配转换：当前状态和字母表中的一个字符相对应且文本中的当前字符和该字符相匹配，自动机可以扫过文本中的该字符转换到下一个状态。</li>
<li>$\epsilon$转换：匹配空字符，转换到另一个状态而不扫描文本中任何文本。 比如* 或 |  等等。</li>
</ul>
<p>所以<strong>不确定性</strong>指的是离开状态的转移可能有多种，即使不扫描任何字符，它在不同时间所进行的状态转移也可能是不同的。</p>
<p>NFA必须能猜测文本的转换才能到接受状态。实际上从给定文本位置0到EOF，如果进行一系列状态转换并最终到达接受状态，则称NFA识别了一个文本字符串，否则扫描所有字符后的NFA处于未接受状态。证明存在性可跟踪NFA处理文本字符串的轨迹，确定转换序列。对于找到一个序列，或者证明不存在这样一个序列，这些问题可以用遍历——即系统地尝试所有可能 解决！</p>
<h2 id="模拟nfa运行">模拟NFA运行<a href="#模拟nfa运行" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h2>
<h4 id="自动机数据结构表示">自动机数据结构表示<a href="#自动机数据结构表示" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h4>
<p>字符数组！存放正则表达式本身，表示了所有状态名，表示了匹配转换！ $\epsilon  $转换由有向图表示！！！</p>
<h4 id="自动机模拟">自动机模拟<a href="#自动机模拟" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h4>
<p>模拟NFA运行轨迹，我们会记录自动机在检查当前输入字符时可能遇到的所有状态集合。<strong>多点可达性</strong>的算法实现是保障了$\epsilon$转换可达的状态集合。初始化集合是由状态0通过$\epsilon$转换可达的状态构成。</p>
<p>往NFA中输入字符，去尝试匹配每一个状态，匹配则进入下一状态。实例NFA中初始状态集合为{0,1,2,3,4,6}，如果第一个输入字符为A，那么NFA通过匹配转换可能到达的状态是{3，7}，然后它可能进行3到2或3到4的$\epsilon$转换，因此可能与第二个字符匹配的状态集合为{2,3,4,7}；迭代上述过程直到文本结束可能有两种结果：</p>
<ul>
<li>含有接受状态</li>
<li>不含有接受状态</li>
</ul>
<blockquote>
<p>最坏情况下的成本为文本和模式的长度之积，这与初级字符串匹配算法的成本是相同的！</p>
</blockquote>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#204a87;font-weight:bold">public</span> <span style="color:#204a87;font-weight:bold">boolean</span> <span style="color:#000">recognizes</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">String</span> <span style="color:#000">txt</span><span style="color:#ce5c00;font-weight:bold">){</span>
        <span style="color:#000">Bag</span><span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">Integer</span><span style="color:#ce5c00;font-weight:bold">&gt;</span> <span style="color:#000">pc</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#204a87;font-weight:bold">new</span> <span style="color:#000">Bag</span><span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">Integer</span><span style="color:#ce5c00;font-weight:bold">&gt;();</span>
        <span style="color:#000">DirectDFS</span> <span style="color:#000">dfs</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#204a87;font-weight:bold">new</span> <span style="color:#000">DirectDFS</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">,</span><span style="color:#000">0</span><span style="color:#ce5c00;font-weight:bold">);</span>

        <span style="color:#204a87;font-weight:bold">for</span> <span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">i</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">0</span><span style="color:#ce5c00;font-weight:bold">;</span> <span style="color:#000">i</span> <span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">txt</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">length</span><span style="color:#ce5c00;font-weight:bold">()</span> <span style="color:#ce5c00;font-weight:bold">;</span> <span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">++)</span> <span style="color:#ce5c00;font-weight:bold">{</span>
            <span style="color:#000">Bag</span><span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">Integer</span><span style="color:#ce5c00;font-weight:bold">&gt;</span> <span style="color:#000">match</span> <span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#204a87;font-weight:bold">new</span> <span style="color:#000">Bag</span><span style="color:#ce5c00;font-weight:bold">&lt;&gt;();</span>
            <span style="color:#204a87;font-weight:bold">for</span> <span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">v</span><span style="color:#ce5c00;font-weight:bold">:</span><span style="color:#000">pc</span><span style="color:#ce5c00;font-weight:bold">)</span> <span style="color:#ce5c00;font-weight:bold">{</span>
                <span style="color:#204a87;font-weight:bold">if</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">v</span><span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">M</span><span style="color:#ce5c00;font-weight:bold">)</span>
                    <span style="color:#204a87;font-weight:bold">if</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">v</span><span style="color:#ce5c00;font-weight:bold">]</span> <span style="color:#ce5c00;font-weight:bold">==</span> <span style="color:#000">txt</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">charAt</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">)</span> <span style="color:#ce5c00;font-weight:bold">||</span> <span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">v</span><span style="color:#ce5c00;font-weight:bold">]==</span><span style="color:#4e9a06">&#39;.&#39;</span><span style="color:#ce5c00;font-weight:bold">)</span>
                        <span style="color:#000">match</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">add</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">v</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">1</span><span style="color:#ce5c00;font-weight:bold">);</span>
            <span style="color:#ce5c00;font-weight:bold">}</span>
            <span style="color:#000">pc</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#204a87;font-weight:bold">new</span> <span style="color:#000">Bag</span><span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">Integer</span><span style="color:#ce5c00;font-weight:bold">&gt;();</span>
            <span style="color:#000">dfs</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#204a87;font-weight:bold">new</span> <span style="color:#000">DirectDFS</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">,</span><span style="color:#000">match</span><span style="color:#ce5c00;font-weight:bold">);</span>
            <span style="color:#204a87;font-weight:bold">for</span> <span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">j</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">0</span><span style="color:#ce5c00;font-weight:bold">;</span> <span style="color:#000">j</span> <span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">V</span><span style="color:#ce5c00;font-weight:bold">()</span> <span style="color:#ce5c00;font-weight:bold">;</span> <span style="color:#000">j</span><span style="color:#ce5c00;font-weight:bold">++)</span> <span style="color:#ce5c00;font-weight:bold">{</span>
                <span style="color:#204a87;font-weight:bold">if</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">dfs</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">marked</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">j</span><span style="color:#ce5c00;font-weight:bold">))</span> <span style="color:#000">pc</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">add</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">j</span><span style="color:#ce5c00;font-weight:bold">);</span>
            <span style="color:#ce5c00;font-weight:bold">}</span>
        <span style="color:#ce5c00;font-weight:bold">}</span>
        <span style="color:#204a87;font-weight:bold">for</span> <span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">v</span><span style="color:#ce5c00;font-weight:bold">:</span> <span style="color:#000">pc</span><span style="color:#ce5c00;font-weight:bold">)</span> <span style="color:#ce5c00;font-weight:bold">{</span>
            <span style="color:#204a87;font-weight:bold">if</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">v</span><span style="color:#ce5c00;font-weight:bold">==</span><span style="color:#000">M</span><span style="color:#ce5c00;font-weight:bold">)</span>
                <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#204a87;font-weight:bold">true</span><span style="color:#ce5c00;font-weight:bold">;</span>
        <span style="color:#ce5c00;font-weight:bold">}</span>
        <span style="color:#204a87;font-weight:bold">return</span> <span style="color:#204a87;font-weight:bold">false</span><span style="color:#ce5c00;font-weight:bold">;</span>
    <span style="color:#ce5c00;font-weight:bold">}</span>
</code></pre></div><h2 id="构造与正则表达式对应的nfa">构造与正则表达式对应的NFA<a href="#构造与正则表达式对应的nfa" class="anchor" aria-hidden="true"><i class="iconfont icon-link"></i></a></h2>
<p>正则表达式转化为NFA过程类似于Dijkstra的双栈算法对算术表达式的处理。</p>
<p>不同之一是正则表达式的构造只要一个栈就可以了！</p>
<p>根据NFA数据结构的表示，字符数组和有向图G一个都不能少。我们将会用栈了记录左括号和或运算符的位置，栈极为擅长处理嵌套结构。</p>
<p>下面给出核心操作构造实现：</p>
<p><strong>连接操作</strong>：太容易实现了！状态的匹配转换和字母表中的字符的对应关系就是连接操作的实现。</p>
<p><strong>括号</strong>：左括号压栈，右括号弹出符号。</p>
<p><strong>闭包操作</strong>：1.*出现在单个字符后，字符于 * 添加两条$\epsilon$转换形成闭环   2.*出现在右括号后，将对应的左括号和 * 之间添加两条$\epsilon$转换形成闭环。</p>
<p><strong>或操作</strong>：作为唯一一个二元操作符，直接放图，还是有向图里的$\epsilon$转换</p>
<p><img src="https://cdn.jsdelivr.net/gh/littlegreedy/zero/img/pic/image-20200819234828514.png" alt=""></p>
<div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-java" data-lang="java"><span style="color:#204a87;font-weight:bold">public</span> <span style="color:#204a87;font-weight:bold">class</span> <span style="color:#000">NFA</span> <span style="color:#ce5c00;font-weight:bold">{</span>
    <span style="color:#204a87;font-weight:bold">private</span> <span style="color:#204a87;font-weight:bold">char</span><span style="color:#ce5c00;font-weight:bold">[]</span> <span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">private</span> <span style="color:#000">DiGraph</span> <span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">;</span>
    <span style="color:#204a87;font-weight:bold">private</span> <span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">M</span><span style="color:#ce5c00;font-weight:bold">;</span>

    <span style="color:#8f5902;font-style:italic">//构造regexp的NFA
</span><span style="color:#8f5902;font-style:italic"></span>    <span style="color:#204a87;font-weight:bold">public</span> <span style="color:#000">NFA</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">String</span> <span style="color:#000">regexp</span><span style="color:#ce5c00;font-weight:bold">){</span>
        <span style="color:#000">Stack</span><span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">Integer</span><span style="color:#ce5c00;font-weight:bold">&gt;</span> <span style="color:#000">ops</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#204a87;font-weight:bold">new</span> <span style="color:#000">Stack</span><span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">Integer</span><span style="color:#ce5c00;font-weight:bold">&gt;();</span>
        <span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#000">regexp</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">toCharArray</span><span style="color:#ce5c00;font-weight:bold">();</span>
        <span style="color:#000">M</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">length</span><span style="color:#ce5c00;font-weight:bold">;</span>
        <span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#204a87;font-weight:bold">new</span> <span style="color:#000">DiGraph</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">M</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">1</span><span style="color:#ce5c00;font-weight:bold">);</span>

        <span style="color:#204a87;font-weight:bold">for</span> <span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">i</span> <span style="color:#ce5c00;font-weight:bold">=</span> <span style="color:#000">0</span><span style="color:#ce5c00;font-weight:bold">;</span> <span style="color:#000">i</span> <span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">M</span> <span style="color:#ce5c00;font-weight:bold">;</span> <span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">++)</span> <span style="color:#ce5c00;font-weight:bold">{</span>
            <span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">lp</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">;</span>
            <span style="color:#204a87;font-weight:bold">if</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">]</span> <span style="color:#ce5c00;font-weight:bold">==</span> <span style="color:#4e9a06">&#39;(&#39;</span> <span style="color:#ce5c00;font-weight:bold">||</span> <span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">]==</span><span style="color:#4e9a06">&#39;|&#39;</span><span style="color:#ce5c00;font-weight:bold">)</span>
                <span style="color:#000">ops</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">push</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">);</span>
            <span style="color:#204a87;font-weight:bold">else</span> <span style="color:#204a87;font-weight:bold">if</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">]==</span><span style="color:#4e9a06">&#39;)&#39;</span><span style="color:#ce5c00;font-weight:bold">){</span>
                <span style="color:#204a87;font-weight:bold">int</span> <span style="color:#000">or</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#000">ops</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">pop</span><span style="color:#ce5c00;font-weight:bold">();</span>
                <span style="color:#204a87;font-weight:bold">if</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">or</span><span style="color:#ce5c00;font-weight:bold">]==</span><span style="color:#4e9a06">&#39;|&#39;</span><span style="color:#ce5c00;font-weight:bold">){</span>
                    <span style="color:#000">lp</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#000">ops</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">pop</span><span style="color:#ce5c00;font-weight:bold">();</span>
                    <span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">addEdge</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#ce5c00;font-weight:bold">,</span><span style="color:#000">or</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">1</span><span style="color:#ce5c00;font-weight:bold">);</span>
                    <span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">addEdge</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">or</span><span style="color:#ce5c00;font-weight:bold">,</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">);</span>
                <span style="color:#ce5c00;font-weight:bold">}</span>
                <span style="color:#204a87;font-weight:bold">else</span> <span style="color:#000">lp</span><span style="color:#ce5c00;font-weight:bold">=</span><span style="color:#000">or</span><span style="color:#ce5c00;font-weight:bold">;</span>
            <span style="color:#ce5c00;font-weight:bold">}</span>
            <span style="color:#204a87;font-weight:bold">if</span><span style="color:#ce5c00;font-weight:bold">(</span> <span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">&lt;</span><span style="color:#000">M</span><span style="color:#ce5c00;font-weight:bold">-</span><span style="color:#000">1</span> <span style="color:#ce5c00;font-weight:bold">&amp;&amp;</span> <span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">1</span><span style="color:#ce5c00;font-weight:bold">]</span> <span style="color:#ce5c00;font-weight:bold">==</span> <span style="color:#4e9a06">&#39;*&#39;</span><span style="color:#ce5c00;font-weight:bold">){</span>
                <span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">addEdge</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">lp</span><span style="color:#ce5c00;font-weight:bold">,</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">1</span><span style="color:#ce5c00;font-weight:bold">);</span>
                <span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">addEdge</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">1</span><span style="color:#ce5c00;font-weight:bold">,</span><span style="color:#000">lp</span><span style="color:#ce5c00;font-weight:bold">);</span>
            <span style="color:#ce5c00;font-weight:bold">}</span>
            <span style="color:#204a87;font-weight:bold">if</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">]</span> <span style="color:#ce5c00;font-weight:bold">==</span> <span style="color:#4e9a06">&#39;(&#39;</span> <span style="color:#ce5c00;font-weight:bold">||</span> <span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">]==</span><span style="color:#4e9a06">&#39;*&#39;</span> <span style="color:#ce5c00;font-weight:bold">||</span> <span style="color:#000">re</span><span style="color:#ce5c00;font-weight:bold">[</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">]==</span> <span style="color:#4e9a06">&#39;)&#39;</span><span style="color:#ce5c00;font-weight:bold">)</span>
                <span style="color:#000">G</span><span style="color:#ce5c00;font-weight:bold">.</span><span style="color:#c4a000">addEdge</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">,</span><span style="color:#000">i</span><span style="color:#ce5c00;font-weight:bold">+</span><span style="color:#000">1</span><span style="color:#ce5c00;font-weight:bold">);</span>
        <span style="color:#ce5c00;font-weight:bold">}</span>
    <span style="color:#ce5c00;font-weight:bold">}</span>

    <span style="color:#204a87;font-weight:bold">public</span> <span style="color:#204a87;font-weight:bold">boolean</span> <span style="color:#000">recognizes</span><span style="color:#ce5c00;font-weight:bold">(</span><span style="color:#000">String</span> <span style="color:#000">txt</span><span style="color:#ce5c00;font-weight:bold">)</span> <span style="color:#8f5902;font-style:italic">//上文
</span><span style="color:#8f5902;font-style:italic"></span><span style="color:#ce5c00;font-weight:bold">}</span>
</code></pre></div>
          </div>
          <div class="card-footer d-print-none">
            <div class="post-nav">
              
              <a class="next-post" href="https://fziks.gitee.io/blog/c&#43;&#43;string/">
                <span class="post-nav-label"><i class="iconfont icon-back-arrow-"></i> 上一篇</span><br><span>C&#43;&#43;字符串简洁处理</span>
              </a>
              
              
            </div>
          </div>
        </div>
      </div>
    </div>
    
    <div id="disqus_thread"></div>
      <script>
      

      

      (function() { 
      var d = document, s = d.createElement('script');
      s.src = "https://"+"your site name on disqus"+".disqus.com/embed.js";
      s.setAttribute('data-timestamp', +new Date());
      (d.head || d.body).appendChild(s);
      })();
      </script>
      <noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>                  
    </div>
    
</div>


    
        <footer id="footer-main">
    <div class="footer-light">
        <div class="container px-0">
            <div class="row align-items-center justify-content-md-between py-4 mt-4 mx-0">
                <div class="col-md-4 mb-3 mb-md-0">
                    <div class="copyright font-weight-bold text-center text-sm text-md-left">
                        <i class="iconfont icon-copyright ficon"></i>
                        2019 - 2020, littlegreedy . All rights reserved.</div>
                </div>
                <div class="col-md-8 d-print-none">
                    <ul class="nav align-items-center justify-content-center justify-content-md-end">
                        <li class="nav-item">
                            <a class="nav-link" href="https://fziks.gitee.io/blog/index.xml" target="_blank">
                                <i class="iconfont icon-rss"></i>
                                Atom Feed
                            </a>
                        </li>
                    
                        <ul class="nav align-items-center justify-content-center justify-content-md-end">
                            <li class="nav-item">
                                <a class="nav-link" href="http://beian.miit.gov.cn" target="_blank">
                                    <i class="iconfont icon-ICPbeianfuwu"></i>
                                    waiting
                                </a>
                            </li>
                            <li class="nav-item">
                                <a class="nav-link" href="http://beian.miit.gov.cn" target="_blank">
                                    <i class="iconfont icon-beian"></i>
                                    waiting
                                </a>
                            </li>
                        </ul>
                    </ul>
                </div>
            </div>
        </div>
</footer>
        <script
    src="https://code.jquery.com/jquery-3.4.1.min.js"
    integrity="sha256-CSXorXvZcTkaix6Yvo6HppcZGetbYMGWSFlBw8HfCJo="
    crossorigin="anonymous"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.14.7/umd/popper.min.js" integrity="sha384-UO2eT0CpHqdSJQ6hJty5KVphtPhzWj9WO1clHTMGa3JDZwrnQq4sF86dIHNDz0W1" crossorigin="anonymous"></script>
    <script src="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/js/bootstrap.min.js" integrity="sha384-JjSmVgyd0p3pXB1rRibZUAYoIIy6OrQ6VrjIEaFf/nJGzIxFDsf4x0xIM+B07jRM" crossorigin="anonymous"></script><script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.1/dist/katex.min.js" integrity="sha384-y23I5Q6l+B6vatafAwxRu/0oK/79VlbSz7Q9aiSZUvyWYIYsd+qj+o24G5ZU2zJz" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.11.1/dist/contrib/auto-render.min.js" integrity="sha384-kWPLUVMOks5AQFrykwIup5lo0m3iMkkHrD0uJ4H5cjeGihAutqP0yW0J6dpFiVkI" crossorigin="anonymous"
onload="renderMathInElement(document.body);"></script>

<script type="text/javascript" src="https://fziks.gitee.io/custom.min.d3e1b7647f32dbe7e0140398739a26dad3f3470fc1eebe0741ef33668f1b7bd0b2917dc6efb9f0d9f1092b91dca502cab1b883863f02530133a8a8ef609926af.js" integrity="sha512-0&#43;G3ZH8y2&#43;fgFAOYc5om2tPzRw/B7r4HQe8zZo8be9CykX3G77nw2fEJK5HcpQLKsbiDhj8CUwEzqKjvYJkmrw=="></script>
<script type="text/javascript">

document.addEventListener("DOMContentLoaded", function () {
    renderMathInElement(
        document.body, {
            delimiters: [
                {
                    left: "$$",
                    right: "$$",
                    display: true
                },
                {
                    left: "\\[",
                    right: "\\]",
                    display: true
                },
                {
                    left: "$",
                    right: "$",
                    display: false
                },
                {
                    left: "\\(",
                    right: "\\)",
                    display: false
                }
            ],
            strict: false
        }
    );
});


$(document).on('click', 'a[href^="#"]', function (event) {
    event.preventDefault();

    $('html, body').animate({
        scrollTop: $($.attr(this, 'href')).offset().top
    }, 500);
});
</script>



   
    
</body>

</html>